Pembinaan jambatan itu dibahagikan kepada enam "pakej" atau kontrak.[3] Yang pertama ialah CC1 atau Terowong Mentiri yang melibatkan pembinaan satu siri terowong melalui Permatang Mentiri yang menghubungkan Jalan Utama Mentiri, jalan dua akses terkawal, dengan Jalan Kota Batu. Pakej pembinaan lain termasuk CC2, CC3 dan CC4 masing-masing terdiri daripada Jejambat Marin, Jambatan Navigasi dan Jejambat Temburong. CC2 dan CC3 telah dianugerahkan kepada Daelim, sebuah syarikat Korea Selatan, yang bertanggungjawab membina sistem jejambat dan dua jambatan kabel yang merentasi Teluk Brunei.[4] Sementara itu, China State Construction Engineering telah dianugerahkan kontrak CC4 dan bertanggungjawab membina jejambat tanah yang merentasi paya bakau Hutan Simpan Labu.[5][6][7][8] CC5A dan CC5B ialah sistem kawalan lalu lintas dan pengawasan, dan sistem bekalan kuasa masing-masing. Projek itu dilaporkan menelan belanja 1.6 bilion ringgit Brunei (AS$1.2 bilion setakat Mac 2018).[2][9]

Pembinaan jambatan itu bermula pada 2014 dan dijangka siap dan dibuka pada penghujung 2019, tetapi akhirnya dibuka pada Mac 2020. Disebabkan oleh wabak COVID-19, jambatan itu dibuka lebih awal daripada jadual pada 17 Mac 2020, sehari selepas Brunei menghalang kebanyakan warga asing bukan pemastautin daripada memasuki negara ini, dan kebanyakan rakyat serta penduduk daripada keluar, yang sebaliknya akan memutuskan sambungan Temburong dari seluruh negara.[10]

Pada 14 Julai 2020, sempena ulang tahun keputeraan Sultan Haji Hassanal Bolkiah yang ke-74, jambatan itu dinamakan Jambatan Sultan Haji Omar 'Ali Saifuddien sebagai penghormatan kepada ayahanda Sultan, Almarhum Sultan Haji Omar 'Ali Saifuddien Saadul Khairi Waddien, yang dikenali secara meluas sebagai arkitek Brunei moden.[11]